'''
Created on Jul 10, 2013

@author: Petko
'''
import sys

class UpdateRange:
    def __init__(self, left, right, offset):
        self.left = left
        self.right = right
        self.offset = offset
        
    def __repr__(self):
        return "<UpdateRange l=%d r=%d o=%d>" % (self.left, self.right, self.offset)
    
class UpdateRagesSet:
    def __init__(self):
        self.ranges = [UpdateRange(1, sys.maxint, 0)]
    
    def __repr__(self):
        return str(self.ranges)
    
    def merge_range(self, new_range):
        assert isinstance(new_range, UpdateRange)
        #we don't support merging ranges other than [left, maxint]
        assert new_range.right == self.ranges[-1].right and new_range.right == sys.maxint
        
        def process_merge(new_rng):
            for rng in self.ranges:
                assert isinstance(rng, UpdateRange)
                if rng.right < new_rng.left:
                    #no change - rng is unaffected by new_rng
                    yield rng
                elif rng.right >= new_rng.left and rng.left < new_rng.left:
                    #split rng into 2 ranges
                    
                    #first range is with the offset of rng
                    r1 = UpdateRange(rng.left, new_rng.left-1, rng.offset)
                    
                    #second range is affected by new_rng
                    r2 = UpdateRange(new_rng.left, rng.right, rng.offset + new_rng.offset)
                    
                    yield r1
                    yield r2
                else :
                    #else affect the previous range with the offset of new_rng
                    rng.offset += new_rng.offset
                    yield rng
                    
        self.ranges = list(process_merge(new_range))
    
    '''
    Returns the index of the range that contains the value x
    Optionally the starting index could not be 0 in case the caller 
    knows that the index of the result will be >= lo 
    @return: the index of the range that contains the value x, -1 if not found
    ''' 
    def find_range_idx(self, x, lo=0):
        hi=len(self.ranges)
        
        while lo < hi:
            mid = (lo+hi)//2
            midval = self.ranges[mid]
            if midval.right < x:
                lo = mid+1
            elif midval.left > x: 
                hi = mid
            else:
                #midval.left <= x <= midval.right
                return mid
        return -1